package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/16 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 字符串全排列 {
    public static void main(String[] args) {
        System.out.println(getAllCasesString("abc"));
    }

    public static List<String> getAllCasesString(String str){
        ArrayList<String> res = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return res;
        }
        char[] chs = str.toCharArray();
        process1(chs, 0, res);
        return res;
    }

//    打印一个字符串的全部排列,process
//    设定 0-i位置已经排列好 abcd
//    考虑 从i开始；
    public static void process1(char[] str, int i, ArrayList<String> ans) {
//        到最终位置（末尾），说明都已确定,加入
        if (i == str.length){
            ans.add(String.valueOf(str)); // 交换到底部了，说明该数组已经生成一个排列，
        }
        for (int j = i; j < str.length; j++) {
            swap(str,i,j); // 从 i 开始 交换 和其下一个位置的元素
            process1(str,i+1,ans); // 开始继续考虑排列：
            swap(str,j,i); // 若交换到底部，说明已经add一个，回退到上一级。

        }


    }

    private static void swap(char[] str, int j, int i) {
        char t = str[i];
        str[i] = str[j];
        str[j] = t;
    }


}
